package com.algorithm.ch1.cjm2.array;

import com.sun.tools.javac.util.Assert;

import java.util.Arrays;

/**
 * Created by jieming.chen on 2019-07-17
 */
public class Rotate {
    public static void main(String[] args) {
        int[] nums = {1,2,3,4,5,6,7};
        int[] nums1 = {-1,-100,3,99};
        int[] res = {5,6,7,1,2,3,4};
        int[] res1 = {3,99,-1,-100};

        rotate3(nums, 3);
        rotate3(nums1, 2);

        System.out.println(Arrays.toString(nums));
        System.out.println(Arrays.toString(nums1));

        Assert.check(Arrays.equals(nums, res));
        Assert.check(Arrays.equals(nums1, res1));
    }

    // 暴力破解
    private static void rotate1(int[] nums, int k) {
        k = k % nums.length;
        for (int i = 0; i < k; i++) {
            int pre = nums[nums.length - 1];
            for (int j = 0; j < nums.length; j++) {
                int temp = nums[j];
                nums[j] = pre;
                pre = temp;
            }
        }
    }

    // 使用额外数组
    private static void rotate2(int[] nums, int k) {
        int[] res = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            res[(i + k) % nums.length] = nums[i];
        }
        for (int i = 0; i < res.length; i++) {
            nums[i] = res[i];
        }
    }

    // 使用环状替换
    private static void rotate3(int[] nums, int k) {
        k = k % nums.length;
        int count = 0;
        for (int start = 0; count < nums.length; start++) {
            int current = start;
            int prev = nums[start];
            do {
                int next = (current + k) % nums.length;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }

    // 使用反转
    private static void rotate4(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length -1);
        reverse(nums, 0, k -1);
        reverse(nums, k, nums.length -1);
    }

    private static void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }




}
